package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 174. 地下城游戏
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/26 11:01
 */
public class CalculateMinimumHP {

    public static void main(String[] args) {
        CalculateMinimumHP test = new CalculateMinimumHP();

        // 7
        int[][] arr = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};

        int i = test.calculateMinimumHP(arr);
        System.out.println(i);
    }

    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0 || dungeon[0].length == 0) {
            return 0;
        }
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] arr = new int[m][n];
        arr[m - 1][n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : 1 - dungeon[m - 1][n - 1];
        for (int i = n - 2; i >= 0; i--) {
            arr[m - 1][i] = arr[m - 1][i + 1] - dungeon[m - 1][i] < 1 ? 1 : arr[m - 1][i + 1] - dungeon[m - 1][i];
        }
        for (int i = m - 2; i >= 0; i--) {
            arr[i][n - 1] = arr[i + 1][n - 1] - dungeon[i][n - 1] < 1 ? 1 : arr[i + 1][n - 1] - dungeon[i][n - 1];
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int a = arr[i][j + 1] - dungeon[i][j] < 1 ? 1 : arr[i][j + 1] - dungeon[i][j];
                int b = arr[i + 1][j] - dungeon[i][j] < 1 ? 1 : arr[i + 1][j] - dungeon[i][j];
                arr[i][j] = Math.min(a, b);
            }
        }
        return arr[0][0];
    }


}
